package www.study.com;

//下一个排列 https://leetcode.cn/problems/next-permutation/
public class code31 {
    public static void main(String[] args) {

    }

    class Solution {
        public void reverse(int[] nums,int i,int j){
            while(i < j){
                swap(nums,i,j);
                i++;
                j--;
            }
        }
        public void swap(int[] nums,int i,int j){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        public void nextPermutation(int[] nums) {
            int i = nums.length - 2;
            while(i != -1 && nums[i] >= nums[i + 1]){ //注意数据会有重复
                i--;
            }
            if(i == -1){
                reverse(nums,0,nums.length - 1);
            }else{
                int pos = nums.length - 1;
                for(int j = nums.length - 1 ; j > -1 ; j--){
                    if(nums[j] > nums[i]){
                        pos = j;
                        break;
                    }
                }
                swap(nums,i,pos);
                reverse(nums,i + 1,nums.length - 1);
            }
        }
    }
}
